Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms

摘要

In most algorithms involving elliptic curves, the most expensive part consists in computing multiples of points. This paper investigates how to extend the tau-adic expansion from Koblitz curves to a larger class of curves defined over a prime field having an efficiently-computable endomorphism phi in order to perform an efficient point multiplication with efficiency similar to Solinas' approach presented at CRYPTO 197. Furthermore, many elliptic curve cryptosystems require the computation of k(0)P + k(1)Q. Following the work of Solinas on the Joint Sparse Form, we introduce the notion of phi-Joint Sparse Form which combines the advantages of a phi-expansion with the additional speedup of the Joint Sparse Form. We also present an efficient algorithm to obtain the phi-Joint Sparse Form. Then, the double exponentiation can be done using the phi endomorphism instead of doubling, resulting in an average of l applications of phi and l/2 additions, where l is the size of the k(i)'s. This results in an important speed-up when the computation of phi is particularly effective, as in the case of Koblitz curves.